/* 最大深度
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]：

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。 来源: LeetCode第104题
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
// #递归实现
var maxDepth = function (root) {
    // 递归终止条件 
    if (root === null) return 0;
    return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
};

// 非递归实现
// 采用层序遍历的方式，非常好理解。
var maxDepth = function (root) {
    if (root === null) return 0;
    const queue = [root];
    let level = 0;
    while (queue.length) {
        let size = queue.length;
        while (size--) {
            const parent = queue.shift();
            if (parent.left) queue.push(parent.left);
            if (parent.right) queue.push(parent.right);
        }
        // level ++ 后的值代表着现在已经处理完了几层节点
        level++;
    }
    return level;
};